Flash memory devices are commonly used as mass data storage subsystems for electronic devices. Such subsystems may be implemented as either removable memory cards that may be inserted into a host system or as non-removable embedded storage within the host system. In both implementations, the subsystem may include one or more flash memory devices and often a flash memory controller.
Flash memory devices are composed of one or more arrays of transistor cells, with each cell capable of non-volatile storage of one or more bits of data. Accordingly, flash memory does not require power to retain data programmed therein. However, once programmed, a cell must be erased before it can be reprogrammed with a new data value. These arrays of cells are partitioned into groups to provide for efficient implementation of read, program (write), and erase functions. A typical flash memory architecture for mass storage arranges groups of cells into erasable blocks, wherein a block includes the smallest number of cells (or unit of erasure) that is erasable at one time. Because a block may contain multiple cells, each block may store multiple data units.
Flash memory is different from other memory used for storage such as hard drives. Flash memory includes unique limitations. First, flash memory has a limited lifetime and exhibits memory wear that can deteriorate the integrity of the storage. Second, because of memory wear, traditional write operations to flash memory can take a comparatively long time due to leveling out potential wear on physical blocks.
Flash memory has a limited lifetime and exhibits memory wear that can deteriorate the integrity of the storage. Each erasable block or segment can be put through a limited number of re-write (“program”) and erase cycles before becoming unreliable. In many cases, a memory controller maintains a logical-to-physical block lookup table to translate the flash memory array “physical block” addresses to “logical block” addresses used by the host system. “Physical blocks” refer to the actual blocks in the flash memory array. “Logical blocks” refer to an abstraction of virtual blocks used by the host system when interacting with the physical blocks via the memory controller. The memory controller uses wear-leveling algorithms to determine which physical block to use each time data is programmed. Logical blocks eliminate the relevance of the physical location of data on the flash memory array and enable data to be stored anywhere within the flash memory array.
Because of memory wear, traditional write operations to flash memory can take a comparatively long time due to leveling out potential wear on physical blocks. This is because a traditional write operation to target a logical block address (LBA) requires the flash memory to use a block-based algorithm. An LBA refers to an identifier, or memory address, for accessing a logical block. The block-based algorithm (1) uses a program operation to write data to a new, unused physical block, (2) updates a logical-to-physical-block lookup table to reference the new physical block, and (3) erases the previous physical block associated with the LBA. These program/erase cycles in the flash memory can take a long time for each write operation requested by the host.
Flash memory may store computer files. A file system manages how files are stored, organized, retrieved, and updated on a computer. In particular, a file system generally allows for the organization of files by defining useful abstractions including file names, file metadata, file security, and file hierarchies such as partitions, drives, folders, and directories. One example file system is the File Allocation Table (FAT) file system. The FAT file system is commonly found on flash memory.
The invention provides techniques for reducing the above-described unique limitations associated with flash memory. Ideally, writing data to a FAT file system on the flash memory can be accommodated by tracking blocks available for storage of additional data (referred to in the present disclosure as “open” blocks), and by updating a table of open blocks that lessens the number of undesirable long-running erase operations required when writing files to a FAT file system.